#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: tree_path.py 
@version:
@time: 2024/01/17

把这个复杂的原始问题分解成一个个规模更小的问题

递归前进段：求一个节点的最长同值路径，需要获得该节点左子树与右子树的最长同值路径，
分别表示为变量left、right，然后判断该节点与其左子节点的数值是否相同。
如果相同，可以将该节点和左子节点之间的边与左子树的最长同值路径相加；
如果不同，那么左子树的最长同值路径对于该节点而言毫无意义，left置为0。
右子树同理


递归返回段：由于变量left和right都等于递归函数A的返回值，因此本实例中的递归函数需要有递归返回段，
返回给上层的应当是左右子树中最长同值路径的较大值。

为什么返回值不是left+right？

因为对于一个节点来说，若以此节点为根节点，那么它的最长同值路径为left+right，但是要返回给上层，说明并不是以该节点为根节点，
而是想要继续以更上层的节点为根节点构造树，所以返回给上层根节点的值是左右子树中最长同值路径的较大值。但是，由于题目中说到，最长同值
路径的数可以以任意节点为根，因此可以另外用一个全局变量通过对比更新，保存任意节点为根节点的最长同值路径的子树。

终止条件：当树节点已经不存在时，返回给上层的值为0，整个递归函数A终止前进，开始回传过程。
"""


class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Btree:
    def __init__(self, node=None):
        self.root = node


value = [4, 4, 5, 4, 1]
node = []
for i in value:
    node.append(Node(i))
b = Btree(node[0])

b.root.left = node[1]
b.root.right = node[2]

b.root.left.left = node[3]
b.root.left.right = node[4]


class Solution:
    max_length = 0

    def main(self, root):
        self.max_length = 0
        self.A(root)
        return self.max_length

    def A(self, root):
        if not root:
            return 0

        left = self.A(root.left)
        right = self.A(root.right)

        if root.left and root.left.val == root.val:
            left += 1
        else:
            left = 0

        if root.right and root.right.val == root.val:
            right += 1
        else:
            right = 0
        self.max_length = max(self.max_length, left + right)
        return max(left, right)


print(Solution().main(node[0]))
